Java HashMap源码学习总结

发表于   |  

Java中HashMap使用非常频繁的数据结构，其源码实现也有很多值得学习参考的地方。这里总结下我的学习，源码基于Jdk1.7，Java8中HashMap有很大的优化改进，再折腾学习。

基本思想

HashMap本身就是一个散列表（也叫哈希表），是根据键（Key）而直接访问在内存存储位置的数据结构。HashMap存储的是Key-Value对，通过计算关于Key的函数，将要查询的Value映射到表中的一个记录访问，这样可以大大加快查找速度。其中映射函数称为散列函数（Hash函数），存放记录的数组称为散列表。当产生冲突时，HashMap将散列到同一个存储位置的所有元素保存在一个链表中。所以HashMap基本数据结构就是数组+链表实现的。
还有就是散列表（HashMap）中的容量(Capacity)和负载因子(Loadfactor)两个参数的理解。容量就是数组的大小，负载因子表示数组的填满程度，当数组中的元素（entry）数目大于Capacity*LoadFactor时候，就要对数组扩容，HashMap中默认会扩大两倍。HashMap默认的Capacity初始值为16，LoadFactor默认初始值为0.75。

HashMap中的数据结构

Entry对象

HashMap中的Entry定义：

1
2
3
4
5
6
static class Entry<K,V> implements Map.Entry<K,V> {
      final K key;
      V value;
      Entry<K,V> next;
      int hash;
  }

Entry对象为HashMap中的内部类，实现了Map.Entry接口。Entry对象其实就是链表节点，一个Key-Value对用一个Entry对象表示。其中key、value存储的自然是键和值，next保存了下一个Entry对象的引用，hash为key对应的Hash值。

HashIterator

HashIterator是HahMap中迭代器的基本实现，然后ValueIterator、KeyIterator、EntryIterator都继承了HashIterator并重写了next()方法，实现了Key、Value和Entry的Iterator访问。理解了HashMap的原理后HashIterator也很容易理解了。首先在HashIterator的构造函数中将index移动到散列表中第一个不为空的bucket，比较重要的方法是nextEntry()方法，其实也就是在bucket上的链表和bucket之间移动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
private abstract class HashIterator<E> implements Iterator<E> {
      Entry<K,V> next;        // next entry to return
      int expectedModCount;   // For fast-fail
      int index;              // current slot
      Entry<K,V> current;     // current entry
      //构造函数
      HashIterator() {
      	//记录迭代初始的entry数目
          expectedModCount = modCount;
          //将index移动到的第一个非空的bucket，即数组中首个非空位置
          if (size > 0) { // advance to first entry
              Entry[] t = table;
              while (index < t.length && (next = t[index++]) == null)
                  ;
          }
      }
      public final boolean hasNext() {
          return next != null;
      }
      final Entry<K,V> nextEntry() {
      	//当有其它线程改变了HashMap的结构（增加或者移除元素），将会抛出ConcurrentModificationException
          if (modCount != expectedModCount)
              throw new ConcurrentModificationException();
          Entry<K,V> e = next;
          if (e == null)
              throw new NoSuchElementException();
          //到了链表末尾
          if ((next = e.next) == null) {
              Entry[] t = table;
              //移动到下一个非空的bucket位置
              while (index < t.length && (next = t[index++]) == null)
                  ;
          }
          current = e;
          return e;
      }

看了HashIterator实现后我们也就理解了HashMap不能按元素的插入顺序来访问了，但JDK中提供了LinkedHashMap来保存元素的插入顺序，其实就是在HashMap的基础上实现了一个循环双向链表。

HashMap中的重要函数实现

get函数实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//get方法
   public V get(Object key) {
       if (key == null)
           return getForNullKey();
       Entry<K,V> entry = getEntry(key);
       return null == entry ? null : entry.getValue();
   }
   //key为null
   private V getForNullKey() {
    if (size == 0) {
        return null;
    }
    //key为null的entrty都放在index为0的bucket
    for (Entry<K,V> e = table[0]; e != null; e = e.next) {
        if (e.key == null)
            return e.value;
    }
    return null;
}
//key不为null时
final Entry<K,V> getEntry(Object key) {
       if (size == 0) {
           return null;
       }
       int hash = (key == null) ? 0 : hash(key);
       //通过hash函数计算的值在对应bucket查找，即遍历链表
       for (Entry<K,V> e = table[indexFor(hash, table.length)];
            e != null;
            e = e.next) {
           Object k;
           if (e.hash == hash &&
               ((k = e.key) == key || (key != null && key.equals(k))))
               return e;
       }
       return null;
   }

put函数实现

put函数会根据key的hash函数值找到对应bucket的下标，若对应的bucket不为空，即发生了冲突，此时需要遍历bucket对应的Entry链表查看要插入的Key是否已经存在，若存在则替换原先的Value，不存在则在该bucket对应的链表头新插入一个Entry节点。若对应的bucket为空，则直接新建Entry存入对应bucket。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public V put(K key, V value) {
    if (table == EMPTY_TABLE) {
        inflateTable(threshold);
    }
    if (key == null)
        return putForNullKey(value);
    int hash = hash(key);
    int i = indexFor(hash, table.length);
    //检查对应bucket是否为空（即是否发生冲突），非空的话则遍历对应链表
    //查看Key是否已经存在
    for (Entry<K,V> e = table[i]; e != null; e = e.next) {
        Object k;
        //若key已存在 则替换原来的Value值
        if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
            V oldValue = e.value;
            e.value = value;
            e.recordAccess(this);
            return oldValue;
        }
    }
    modCount++;
    //否则使用头插法在链表头插入Entry
    addEntry(hash, key, value, i);
    return null;
}
//key不存在，则添加Entry
void addEntry(int hash, K key, V value, int bucketIndex) {
	//达到负载程度 需要扩容
    if ((size >= threshold) && (null != table[bucketIndex])) {
        //原表基础上扩大两倍
        resize(2 * table.length);
        hash = (null != key) ? hash(key) : 0;
        bucketIndex = indexFor(hash, table.length);
    }
    createEntry(hash, key, value, bucketIndex);
}
//创建Entry对象 使用头插法插入对应bucket的链表
void createEntry(int hash, K key, V value, int bucketIndex) {
    Entry<K,V> e = table[bucketIndex];
    table[bucketIndex] = new Entry<>(hash, key, value, e);
    size++;
}

hash函数实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
final int hash(Object k) {
    int h = hashSeed;
    if (0 != h && k instanceof String) {
        return sun.misc.Hashing.stringHash32((String) k);
    }
    h ^= k.hashCode();
    // This function ensures that hashCodes that differ only by
    // constant multiples at each bit position have a bounded
    // number of collisions (approximately 8 at default load factor).
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

总结

HashMap与HashTable

HashTable是早期JDK版本中的数据结构，现在已经基本不再使用了，HashMap与HasTable原理基本相同。主要区别除了HashMap在性能上的改进之外，还体现在:

1、HashMap支持key和Value为null，而HashTable中不支持；
2、HashTable是线程安全的，而HashMap非线程安全;

HashMap工作原理

HashMap是基于散列表的实现，结合了数组和链表的优点。HashMap中通过put和get存储和获取对象。存储对象时，我们将Key-Value传给put方法，它调用hashCode计算hash值从而得到bucket位置，进一步存储，在put方法中HashMap会根据当前bucket的占用情况自动调整容量(超过Load Facotr则resize为原来的2倍)；如果存储对象发生碰撞的时候，Hashmap通过链表将产生碰撞冲突的元素组织起来，在Java 8中，如果一个bucket中碰撞冲突的元素超过某个限制(默认是8)，则使用红黑树来替换链表，从而提高速度。。获取对象时，我们将Key传给get，它调用hashCode计算hash从而得到bucket位置，并进一步调用equals()方法确定键值对。

参考

*http://yikun.github.io/2015/04/01/Java-HashMap%E5%B7%A5%E4%BD%9C%E5%8E%9F%E7%90%86%E5%8F%8A%E5%AE%9E%E7%8E%B0/#6-_resize的实现